package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/07/22 22:08
 **/
public class Day7_1_Num62_UniquePaths {
    // 方法一：动态规划
    class Solution {
        public int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            for(int i = 0;i < m;i++){
                dp[i][0] = 1;
            }
            for(int j = 0;j < n;j++){
                dp[0][j] = 1;
            }
            for(int i = 1;i < m;i++){
                for(int j = 1;j < n;j++){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m-1][n-1];
        }
    }

    // 超出时间限制
    class Solution2 {
        public int uniquePaths(int m, int n) {
            return dfs(0, 0, m, n);
        }
        public int dfs(int i, int j, int m, int n){
            if(i >= m || j >= n){
                return 0;
            }
            if(i == m - 1 && j == n - 1){
                return 1;
            }
            return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
        }
    }
}